Time division multiple access encoded information is transmitted in multiple channels per carrier. In accordance with the Group Special Mobile (GSM) standard, there are eight channels per carrier. Each channel is provided a time period for transmission called a transmission burst. Some of the bits in each transmission burst are set aside as training bits for system use.
A Viterbi decoder is a maximum likelihood decoder that provides forward error correction. Viterbi decoders are used to decode a sequence of encoded symbols, such as a bit stream. The bit stream can represent encoded information in a telecommunication system. Such information can be transmitted through various media with each bit (or set of bits) representing a symbol instant. In the decoding process, the Viterbi decoder works back through a sequence of possible bit sequences at each symbol instant to determine which one bit sequence is most likely to have been transmitted. The possible transitions from a bit at one symbol instant, or state, to a bit at a next, subsequent, symbol instant or state is limited. Each possible transition from one state to a next state can be shown graphically and is defined as a branch. A sequence of interconnected branches is defined as a path. Each state can transition only to a limited number of next states upon receipt of the next bit in the bit stream. Thus, some paths survive and other paths do not survive during the decoding process. By eliminating those transitions that are not permissible, computational efficiency can be increased in determining the most likely paths to survive. The Viterbi decoder typically defines and calculates a branch metric associated with each branch and employs this branch metric to determine which paths survive and which paths do not survive.
A branch metric is calculated at each symbol instant for each possible branch. Each path has an associated metric, accumulated cost, that is updated at each symbol instant. For each possible transition, the accumulated cost for the next state is calculated as the lesser of the sum of the branch metric for the possible transitions and the path accumulated cost at the previous state.
While several paths survive the transition from one symbol instant to the next symbol instant, there is only one minimum accumulated cost path from the least of the minimum accumulated costs at a symbol instant, back through the possible branches. Surviving branch data at sequential symbol instants is stored in an array. Identifying the minimum accumulated cost path through the surviving branch data starting with a given symbol instant and extending through previous symbol instants is referred to as a traceback. Typical prior art applications employed a single traceback. The number of symbol instants back through the array that the minimum accumulated cost path extends is the length, or depth, of the traceback. The individual state in the array associated with the minimum accumulated cost at the end of the traceback is translated into the most likely bit to have been transmitted in that symbol instant. This is referred to as a decoded symbol. The longer the traceback length, the greater the accuracy in determining a decoded symbol.
At each symbol instant during the construction of a matrix of surviving branch data, an update operation is followed by a traceback. A latency of symbol instants equal to the traceback length occurs before a valid decoded symbol is obtained. The traceback typically has a fixed length. When the matrix of surviving branch data is complete, it is necessary to obtain the remaining decoded symbols, equal in number to the traceback length, from the matrix. A need remains in the art for a technique to obtain the remaining decoded symbols after the matrix of surviving branch data is complete.